DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.1

Graph Searches and Their End Vertices

Authors: Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

Graph search, the process of visiting vertices in a graph in a specific order, has demonstrated magical powers in many important algorithms. But a systematic study was only initiated by Corneil et al. a decade ago, and only by then we started to realize how little we understand it. Even the apparently naïve question "which vertex can be the last visited by a graph search algorithm," known as the end vertex problem, turns out to be quite elusive. We give a full picture of all maximum cardinality searches on chordal graphs, which implies a polynomial-time algorithm for the end vertex problem of maximum cardinality search. It is complemented by a proof of NP-completeness of the same problem on weakly chordal graphs. We also show linear-time algorithms for deciding end vertices of breadth-first searches on interval graphs, and end vertices of lexicographic depth-first searches on chordal graphs. Finally, we present 2^n * n^O(1)-time algorithms for deciding the end vertices of breadth-first searches, depth-first searches, and maximum cardinality searches on general graphs.

Cite as

Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang. Graph Searches and Their End Vertices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2019.1,
  author =	{Cao, Yixin and Wang, Zhifeng and Rong, Guozhen and Wang, Jianxin},
  title =	{{Graph Searches and Their End Vertices}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.1},
  URN =		{urn:nbn:de:0030-drops-114973},
  doi =		{10.4230/LIPIcs.ISAAC.2019.1},
  annote =	{Keywords: maximum cardinality search, (lexicographic) breadth-first search, (lexicographic) depth-first search, chordal graph, weighted clique graph, end vertex}
}

Search Results

Documents authored by Wang, Zhifeng

Graph Searches and Their End Vertices

Abstract

Cite as

Thanks for your feedback!

Could not send message